﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace StringMatch.MatchAlgorithms
{
    public static class FiniteAutomaton
    {
        /// <summary>
        /// Returns a list of starting indexes of each instance of the pattern found in the text. Uses a finite automaton to perform the search
        /// </summary>
        /// <param name="pattern"></param>
        /// <param name="text"></param>
        /// <returns></returns>
        public static List<int> Match(string pattern, string text)
        {
            List<int> result = new List<int>();
            Dictionary<char,int[]> FA = Transition(pattern);
            int state = 0;

            for (int i = 0; i < text.Length; i++)
            {
                char c = text[i];


                if (!FA.ContainsKey(text[i]))
                    state = 0;
                else
                    state = FA[text[i]][state];

                if (state == pattern.Length)
                {
                    //If we get a match add the index of the start to the result array
                    result.Add(i - pattern.Length+1);
                    //and set the state as though we had failed on the last letter
                    state = 0;//pattern.Length - 1;
                }
            }

            return result;
        }

        /// <summary>
        /// Generates the FA
        /// </summary>
        /// <param name="pattern"></param>
        /// <returns></returns>
        private static Dictionary<char,int[]> Transition(string pattern)
        {
            //<next char, int[current state] = next state>
            Dictionary<char, int[]> result = new Dictionary<char, int[]>();
            string alphabet = GetAlphabet(pattern);
            int k;
            string suffix;
            string prefix;

            for (int q = 0; q < pattern.Length; q++)
            {
                foreach (char c in alphabet)
                {
                    //give it a spot in the dictionary
                    if(!result.ContainsKey(c))
                        result.Add(c, new int[pattern.Length]);

                    //find the greatest suffix of pattern+nextchar that is a prefix of pattern
                    k = Math.Min(pattern.Length, q + 1);
                    
                    suffix = pattern.Substring(0, q);
                    suffix += c;
                    prefix = pattern.Substring(0, k);
                    while (prefix != suffix)
                    {
                        //if the prefix of the pattern does not match the suffix of the pattern + the next character then squeeze down the prefix and the suffix
                        k--;
                        prefix = pattern.Substring(0, k);
                        suffix = suffix.Substring(suffix.Length - k, k);
                    }
                    result[c][q] = k;
                }
            }

            return result;
        }

        /// <summary>
        /// Pulls out the alphabet of the pattern
        /// </summary>
        /// <param name="pattern"></param>
        /// <returns></returns>
        private static string GetAlphabet(string pattern)
        {

            StringBuilder sb = new StringBuilder();
            //for each letter in the pattern
            for (int i = 0; i < pattern.Length; i++)
                //check if it has alreay been added to the result
                if (!sb.ToString().Contains(pattern[i]))
                    sb.Append(pattern[i]);

            return sb.ToString();
        }

    }
}
